/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-11-14
 * Time: 19:06
 */
class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
    
    @Override
    public String toString () {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}
public class Solution {
    /*public ListNode reverseList(ListNode head) {
        //递归
        if(head == null || head.next==null){
            return head;
        }
        ListNode last=reverseList( head.next );
        head.next.next=head;
        head.next=null;
        return last;
    }*/
    
    //双指针法
    public static ListNode reverseList(ListNode head) {
        ListNode newNode=null;
        ListNode cur=head;
        while ( cur!=null ){  //如果条件为cur.next==null，那么prev还没有到达最后一个节点，而是在倒数第二个节点
            //先存储下一节点
            ListNode curNext=cur.next;
            //改变当前节点的指向为前一个节点
            cur.next=newNode;
            newNode=cur;
            cur=curNext;
        }
        return newNode;
    }
    
    public static void main (String[] args) {
        ListNode root=new ListNode( 1 );
        root.next=new ListNode( 2 );
        root.next.next=new ListNode( 3 );
        System.out.println( reverseList( root ) );
    
    }
}
